#pragma once
#include<iostream>
#include<assert.h>

template<class T>
struct double_list_node
{
    double_list_node<T>* _next;
    double_list_node<T>* _prev;
    T _val;
    double_list_node(const T& val)
    :_val(val),_next(nullptr), _prev(nullptr)
    {}
};

template<class T>
class double_list
{
    typedef double_list_node<T> Node;
public:
    double_list()
    :head(new Node(T()))
    {
        head->_next = head;
        head->_prev = head;
    }
    bool empty()
    {
        return head->_next == head;
    }
    Node* find(T val)
    {
        assert(!empty());
        Node* cur = head->_next;

        while (cur != head)
        {
            if(cur->_val == val)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;        
    }
    bool pushTail(T val)
    {
        //哨兵节点前面插入
        return insert(head, val);
    }
    bool pushFront(T val)
    {
        return insert(head->_next, val);
    }
    bool popFront()//头删
    {
        return pop(head->_next);
    }
    bool popTail()//尾删
    {
        return pop(head->_prev);
    }
    //在目标节点前插入节点
    bool insert(Node* target, T val)
    {
        assert(target);
        Node* newNode = new Node(val);

        newNode->_next = target;
        newNode->_prev = target->_prev;

        target->_prev->_next = newNode;
        target->_prev = newNode;
        return true;
    }
    //删除目标节点
    bool pop(Node* target)
    {
        assert(target);
        assert(!empty());
        Node* prev = target->_prev;

        prev->_next = target->_next;
        target->_next->_prev = prev;

        delete target;
        return true;
    }
    void clear()
    {
        Node* cur = head->_next;
        while(cur != head)
        {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        head->_next = head;
        head->_prev = head;
    }
    void Print()
    {
        Node* cur = head->_next;
        while(cur != head)
        {
            std::cout<<cur->_val<<" ";
            cur = cur->_next;
        }
        std::cout << std::endl;
    }
    ~double_list()
    {
        clear();
        delete head;
    }
private:
    Node* head;
};
